package zuo.algo.c06;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

import java.util.LinkedList;

/**
 * 01:09-二叉树非递归遍历
 */
public class TreeTraversal2 {

    public static void cycle(TreeNode root) {
        if (root == null) {
            return;
        }
        cycleFirst(root);
        System.out.println();
        cycleInfix(root);
        System.out.println();
        cycleAfter(root);
        System.out.println();
        level(root);
    }

    public static void cycleFirst(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode node;
        while ((node = stack.poll()) != null) {
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public static void cycleInfix(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.poll();
                System.out.print(node.val + " ");
                node = node.right;
            }
        }
    }

    /**
     * 中序遍历易于理解版
     * 将树的左边全部压到栈里去，弹出时打印该节点并对该节点的右树重复该操作
     */
    public static void cycleInfix1(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        pushLeftNode(stack, root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.poll();
            System.out.print(node.val + " ");
            if (node.right != null) {
                pushLeftNode(stack, node.right);
            }
        }
        System.out.println();
    }

    public static void pushLeftNode(LinkedList<TreeNode> stack, TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    /**
     * 前序：中左右 - 中右左 - 反转成左右中
     */
    public static void cycleAfter(TreeNode root) {
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<TreeNode> stack2 = new LinkedList<>();
        stack1.push(root);
        TreeNode node;
        while ((node = stack1.poll()) != null) {
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while ((node = stack2.poll()) != null) {
            System.out.print(node.val + " ");
        }
    }

    public static void level(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode level = root;
        TreeNode node;
        while ((node = queue.poll()) != null) {
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            if (level == node) {
                System.out.println();
                level = queue.peekLast();
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtils.getTree();
        cycle(root);
        cycleInfix1(root);
    }
}
